/*
 * @lc app=leetcode.cn id=76 lang=cpp
 *
 * [76] 最小覆盖子串
 */

// @lc code=start
class Solution
{
public:
    string minWindow(string s, string t)
    {
        //这里是学习滑动窗口后的练习题
        //返回s中包含t中所有字符的子串
        //首先是很明显的滑动窗口 但是为了判断是否结束需要一个哈希表
        //这里实际上解决了无重复字符的问题 但是如果出现字符重复的情况就不行了
        //这里应该不能直接使用map  需要使用vector
        //用一个vector保存是否需要 和需要几个
        vector<int> need(128, 0); //因为字母可以用气ASCII码表示
        int start = 0;
        int sum = 0;
        int len = __INT32_MAX__;
        int res = 0; //保存开头
        for (int i = 0; i < t.length(); i++)
        {
            //给need赋初值
            need[t[i]]++;
        }
        for (int end = 0; end < s.length(); end++)
        {
            char c = s[end];
            if (need[c] > 0)
            {
                //如果存在在t中
                sum++;
            }
            need[c]--; //当前元素
            while (start <= end && sum == t.length())
            {
                //当前已经满足条件 需要移动起点
                char cc = s[start];
                if (end - start + 1 < len)
                {
                    len = end - start + 1;
                    res = start;
                }

                //一种情况 如果need[cc]<0 说明要么是无用元素 要么就是有多余可以被删除
                if (need[cc] < 0)
                {
                    need[cc]++;
                    start++;
                }
                else
                {
                    //该元素不能删除
                    break;
                }
            }
        }
        return len == __INT32_MAX__ ? "" : s.substr(res, len);
    }
};
// @lc code=end
